2023-03-25-2维DP四边形不等式优化(决策单调性优化)

对于区间DP问题，都可以列出转移方程：

其中

令 表示使 最优的

如果 满足：

1. 区间包含单调性： 对于所有
2. 四边形不等式： 对于所有

那么对于所有 有

这样在枚举决策就只用枚举 到 了

当然，要注意边界情况，即 和

显然这会让复杂度从 降低到 （均摊枚举决策的循环）

证明在这篇论文里（这个优化英文叫 Knuth-Yao quadruple inequality speed-up）

就算与也有关，只要它的前两个参数满足上面两个条件，优化还是能用，证明在这篇论文里

struct Opt {
    int v, k;
} f[N][N];

int F(int i, int j, int k);

void DP() {
    for (int i = 1; i <= n; i++) {
        f[i][i] = (Opt){0, -1};
        for (int j = i + 1; j <= n; j++) {
            f[i][j] = (Opt){1 << 30, -1};
        }
    }
    for (int i = 1; i < n; i++) {
        f[i][i+1] = (Opt){F(i, i+1, i), i};
    }
    for (int len = 3; len <= n; len++) {
        for (int i = 1, j = len; j <= n; i++, j++) {
            int kl = f[i][j - 1].k;
            int kr = f[i + 1][j].k;
            for (int k = kl; k <= kr; k++) {
                int v = F(i, j, k);
                if (v <= f[i][j].v) {
                    f[i][j] = (Opt){v, k};
                }
            }
        }
    }
    printf("%d\n", f[1][n].v);
}
Copy